/*
 * Copyright 北京航空航天大学  @ 2015 版权所有
 */
package com.buaa.edu.leetcode.algorithm.string;

import org.junit.Test;

/**
 * <p>
 * 字符串相乘，假设输入字符串为整数
 * </p>
 * @author towan
 * @email tongwenzide@163.com
 * @time 2015年6月14日
 */
public class MultiplyStrings {
    //error over boundary
/*    public String multiply(String num1, String num2) {
        Long i = Long.valueOf(num1)*Long.valueOf(num2);
        return i.toString();
    }
*/   
    public String multiply(String num1, String num2) {
        int len1 = num1.length();
        int len2 = num2.length();
        int []num = new int[len1+len2];
        int n = num.length;
        for(int i=len1-1;i>=0;i--){
            for(int j=len2-1;j>=0;j--){
                //不考虑进位，模拟乘法
                num[i+j+1] += (num1.charAt(i)-'0')*(num2.charAt(j)-'0');
            }
        }
        //确保每个数位的大小在0-9之间
        int carry = 0;
        for(int i=n-1;i>=0;i--){
            num[i] += carry;
            carry = num[i]/10;
            num[i] = num[i]%10;
        }
        String result = "";
        boolean firstNonZero = false;
        //将数组转化为字符串，如果第一位是0那么去掉
        for(int i=0;i<n;i++){
            //找到第一个非零数字
            if(!firstNonZero && num[i]==0){
                continue;
            }else{
                result+=num[i];
                firstNonZero = true;
            }
        }
        if(result.equals("")){
            return "0";
        }
        return result;
    }

    @Test
    public void testNumberFormatException(){
        //"6913259244", "71103343"
        String num1 = "6913259244";
        String num2 = "71103343";
        String multiply = multiply(num1, num2);
        System.out.println(multiply);
    }
    @Test
    public void test2(){
        //"401716832807512840963", "167141802233061013023557397451289113296441069"
        String num1 = "401716832807512840963";
        String num2 = "167141802233061013023557397451289113296441069";
        String multiply = multiply(num1, num2);
        System.out.println(multiply);
    }
    
}
